class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        bool placed = false;
        vector<vector<int>> res;
        for (int i = 0; i < intervals.size(); ++i)
        {
            vector<int> interval = intervals[i];
            if (interval[0] > right)
            {
                // 当前区间在 newInterval 右侧，且无交集
                if (!placed)
                {
                    res.push_back({left, right});
                    placed = true;
                }
                res.push_back(interval);
            }
            else if (interval[1] < left)
            {
                // 当前区间在 newInterval 左侧，且无交集
                res.push_back(interval);
            }
            else // 有交集，合并
            {
                left = min(left, interval[0]);
                right = max(right, interval[1]);
            }
        }
        // 如果还没插入，说明应插入到最后
        if (!placed)
            res.push_back({left, right});
        return res;
    }
};

/*
class Solution {
public:
    static bool compare(vector<int> a, vector<int> b) {
        return a[0] < b[0];
    }
    
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        if (intervals.empty()) {
            return {newInterval};
        }
        
        vector<vector<int>> res;
        intervals.push_back(newInterval);  // 先把新区间插入末尾
        sort(intervals.begin(), intervals.end(), compare);  // 按左端点排序
        
        for (int i = 0; i < intervals.size() - 1; ++i)
        {
            if (intervals[i][1] >= intervals[i + 1][0])
            {
                intervals[i + 1][0] = intervals[i][0];
                intervals[i + 1][1] = max(intervals[i][1], intervals[i + 1][1]);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        res.push_back(intervals.back());  // 加入最后一个合并后的区间
        return res;
    }
};
*/